package summary;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;

/**
 * @Author: 海琳琦
 * @Date: 2022/4/7 22:22
 */
public class Title621 {

    static class Task {
        int nextTime;

        int restNumber;

        public Task(int nextTime, int restNumber) {
            this.nextTime = nextTime;
            this.restNumber = restNumber;
        }
    }

    public static int leastInterval(char[] tasks, int n) {
        int[] nums = new int[26];
        for (char c : tasks) {
            nums[c - 'A']++;
        }
        //选择不在冷却且时剩余执行任务次数最多的任务
        List<Task> list= new ArrayList<>();
        for (int num : nums) {
            if (num == 0) {
                continue;
            }
            list.add(new Task(0, num));
        }
        list.sort((a, b) -> (Integer.compare(b.restNumber, a.restNumber)));
        int time = 0;
        //起始时随便找一个剩余执行次数最大的任务开始
        while (!list.isEmpty()) {
            //选择不在冷却且时剩余执行任务次数最多的任务
            ////满足 nextValid <= time  and rest 最大
            for (int i = 0; i < list.size(); i++) {
                //判断是否在冷却时间
                Task task = list.get(i);
                if (task.nextTime <= time) {
                    if (task.restNumber > 1) {
                        task.restNumber--;
                        task.nextTime = time + n + 1;
                        list.sort((a, b) -> (Integer.compare(b.restNumber, a.restNumber)));
                    }else{
                        list.remove(i);
                    }
                    break;
                }
            }
            time++;
        }
        return time;
    }

    /**
     * 解题思路：
     *      1、将任务按类型分组，正好A-Z用一个int[26]保存任务类型个数
     *      2、对数组进行排序，优先排列个数（count）最大的任务，
     *           如题得到的时间至少为 retCount =（count-1）* (n+1) + 1 ==> A->X->X->A->X->X->A(X为其他任务或者待命)
     *      3、再排序下一个任务，如果下一个任务B个数和最大任务数一致，
     *           则retCount++ ==> A->B->X->A->B->X->A->B
     *      4、如果空位都插满之后还有任务，那就随便在这些间隔里面插入就可以，因为间隔长度肯定会大于n，在这种情况下就是任务的总数是最小所需时间
     * @param tasks
     * @param n
     * @return
     */
    public static int leastInterval1(char[] tasks, int n) {
        //统计单词的个数
        int[] nums = new int[26];
        for (int i = 0; i < tasks.length; i++) {
            nums[tasks[i] - 'A']++;
        }
        //从小到大排列
        Arrays.sort(nums);
        //优先排列个数最大的任务 因为相同元素必须有n个冷却时间，假设A出现3次，n = 2，任务要执行完，至少形成AXX AXX A序列
        int sum = (nums[25] - 1) * (n + 1) + 1;
        for (int start = 24; start >= 0; start--) {
            //剩余的任务次数有两种情况：
            //1.与A出现次数相同，那么B任务最优插入结果是ABX ABX AB，中间还剩两个空位，当前序列长度+1
            //2.比A出现次数少，若还有X，则按序插入X位置，比如C出现两次，形成ABC ABC AB的序列
            //直到X预占位置还没插满，剩余元素逐个放入X位置就满足冷却时间至少为n
            if (nums[start] == nums[25]) {
                sum++;
            } else {
                break;
            }
        }
        //在任意插满区间（这里是ABC）后面按序插入剩余元素，比如ABCD ABCD发现D之间距离至少为n+1，肯定满足冷却条件
        //因此，当X预占位置能插满时，最短序列长度就是task.length，不能插满则取最少预占序列长度
        return Math.max(sum, tasks.length);
    }

    public static void main(String[] args) {
        char[] tasks = {'A','B','C','D','E','F','G'};
        int n = 2;
        int i = leastInterval(tasks, n);
        System.out.println(i);
    }
}
